package done.normal_201_300;

import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 300. Longest Increasing Subsequence 最长上升子序列
 * <p>
 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
 * <p>
 * 示例:
 * 输入: [10, 9, 2, 5, 3, 7, 101, 18]
 * 输出: 4
 * 解释: 最长的上升子序列是 [2, 3, 7, 101]，它的长度是 4。
 * <p>
 * 2019-05-19 00:24
 **/
@SuppressWarnings("all")
public class LongestIncreasingSubsequence {

    public int lengthOfLIS(int[] nums) {
        // 190519 first
        return -1;
    }

    @Test
    public void test() {
        info(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
//        Integer[] arr = new Integer[]{1,2,3};
//        Arrays.sort(arr, (a,b)->a<b?1:-1);
//        info(arr);
    }
}



























/*
public int lengthOfLIS(int[] nums) {
    // dp[i]: 所有长度为i+1的递增子序列中, 最小的那个序列尾数.
    // 由定义知dp数组必然是一个递增数组, 可以用 maxL 来表示最长递增子序列的长度.
    // 对数组进行迭代, 依次判断每个数num将其插入dp数组相应的位置:
    // 1. num > dp[maxL], 表示num比所有已知递增序列的尾数都大, 将num添加入dp
    // 数组尾部, 并将最长递增序列长度maxL加1
    // 2. dp[i-1] < num <= dp[i], 只更新相应的dp[i]
    int res = 0;
    for (int num : nums) {
        int lo = 0;
        int hi = res;
        while (lo < hi) {
            int mid = lo + (hi-lo)/2;
            if (nums[mid] < num)
                lo = mid + 1;
            else
                hi = mid;
        }

        nums[lo] = num;
        if (lo == res)
            res++;
    }
    return res;
}
*/
